package com.wlj.utils.suanfa;

import com.google.common.collect.Lists;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给一个非空字符串s和一个字符串数组wordDict，问能否使用wordDict中的不同字符串首尾相接，组成s。假设wordDict中没有重复字符串
 * 如: s="leetcode"  ,dict=["leet","code"]，返回true
 */
public class Suanfa08 {


    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dq = new boolean[s.length() + 1];
        dq[0]=true;
        //dq[i]表示 [0,i)范围内的字符串是否可以由dict元素组成
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if(dq[j]&&wordDictSet.contains(s.substring(j,i))){
                    dq[i]=true;
                    break;
                }
            }
        }
        return dq[s.length()];
    }


    public static int target_sum(int nums[],int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < S || (sum + S) % 2 == 1) {
            return 0;
        }
        int w = (sum + S) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = w; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[w];
    }



    public static void main(String[] args) {
        String s="applepenapple";
        String ss[]={"apple","pen"};
        System.out.println(wordBreak(s,Lists.newArrayList(ss)));


        int nums[]={1,1,1,1,1};
        System.out.println(target_sum(nums,1));
    }

}
